/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Mar 27, 2014
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a binary tree, determine if it is a valid binary search
 *              tree (BST).
 * 
 *              Assume a BST is defined as follows:
 * 
 *              The left subtree of a node contains only nodes with keys less
 *              than the node's key. The right subtree of a node contains only
 *              nodes with keys greater than the node's key. Both the left and
 *              right subtrees must also be binary search trees.
 */
public class ValidateBinarySearchTree {

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
	
	public boolean isValidBST(TreeNode root) {
		return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	
	public boolean isValidBST(TreeNode root, int min, int max) {
		if (root == null)
			return true;

		if (root.val < max && root.val > min && isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max))
			return true;
			
		return false;
	}
	
	@Test
	public void test() {
		TreeNode root = new TreeNode(4);
		root.left = new TreeNode(2);
		root.right = new TreeNode(6);
		root.left.left = new TreeNode(1);
		root.left.right = new TreeNode(3);
		root.right.left = new TreeNode(5);
		root.right.right = new TreeNode(7);
		
		assert isValidBST(root) == true;
	}
}
